Design HashMap

Try to solve the Design HashMap problem.

Statement#

Design a hash map without using the built-in libraries. We only need to cater integer keys and integer values in the hash map. Return NULL if the key doesn’t exist.

It should support the following three primary functions of a hash map:

  • Put(key, value): This function inserts a key and value pair into the hash map. If the key is already present in the map, then the value is updated. Otherwise, it is added to the bucket.

  • Get(key): This function returns the value to which the key is mapped. It returns −1-1, if no mapping for the key exists.

  • Remove(key): This function removes the key and its mapped value.

Constraints:

  • 00 ≤\le key ≤\le 10610^6
  • 00 ≤\le value ≤\le 10610^6
  • At most 10410^4 calls can be made to Put(), Get(), and Remove() functions.

Examples#

Created with Fabric.js 3.6.6 Input Output Sample example 1 Put(1, 1) Get(1) Result of Get(1) = 1

1 of 2

Created with Fabric.js 3.6.6 Input Output Sample example 2 Put(1, 1) Put(2, 1) Put(1, 6) Put(7, 8) Get(1) Get(8) Result of Get(1) = 6 Result of Get(8) = -1

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Design HashMap

2

Consider the above hash map where the key-value pairs are mapped according to their respective hash keys, and the modulus base is 11. What will the value mapped to the key 10 be after the function below is called?

Put(10, 300)
Put(10, 200)
Put(10, 600)
Remove(10)
Your Answer
A)

200

B)

300

C)

600

Correct Answer
D)

None of the above

Explanation

After three successive put calls, the value that will be mapped to 10 is 600. When remove is called, both 10 and 600 are removed from the hash map.

Question 2 of 22 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Select a prime number (preferably a large one) as the key space.

Initialize an array with empty buckets (empty arrays). The number of buckets in the array should be equal to the specified value of the key space variable.

Generate a hash key by taking the modulus of the input key with the key space variable.

Perform the appropriate function (Put(), Get(), Remove()).


Try it yourself#

Implement your solution in hash_map.py and bucket.py in the following coding playground.

Python
hash_map.py
bucket.py
Powered by AI
Input #1
Input #2
Design HashMap

Hash Maps: Introduction

Solution: Design HashMap